package com.fwpsl.sort;

import java.util.Arrays;

/**
 * @author: 风戏fw
 * @date: 2024/3/29
 * @description:
 */
public class MargeSort {

    private static void margeSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }

        int[] tempArr = new int[arr.length];
        margeSort(arr, tempArr, 0, arr.length - 1);
    }

    private static void margeSort(int[] arr, int[] tempArr, int left, int right) {
        if (left >= right) {
            return;
        }

        int middle = (left + right) >> 1;
        margeSort(arr, tempArr, left, middle);
        margeSort(arr, tempArr, middle + 1, right);
        margeSortArray(arr, tempArr, left, middle, right);

    }

    private static void margeSortArray(int[] arr, int[] tempArr, int left, int middle, int right) {
        int index1 = left;
        int index2 = middle + 1;
        int tempIndex = left;

        // 将两个有序列表按顺序放入temp数组
        while (index1 <= middle && index2 <= right) {
            tempArr[tempIndex++] = arr[index1] <= arr[index2] ? arr[index1++] : arr[index2++];
        }

        // 只有一个有序列表时（减少比较逻辑）
        while (index1 <= middle) {
            tempArr[tempIndex++] = arr[index1++];
        }

        // 只有一个有序列表时（减少比较逻辑）
        while (index2 <= right) {
            tempArr[tempIndex++] = arr[index2++];
        }

        // 把数据复制回原数组
        for (int i = left; i <= right; i++) {
            arr[i] = tempArr[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {20, 30, 90, 40, 70, 110, 60, 10, 100, 50, 80};
        System.out.println("before sort:" + Arrays.toString(arr));

        // 升序排列
        margeSort(arr);

        System.out.println("after sort:" + Arrays.toString(arr));
    }
}
